package now_coder.greedy.solutions;

import now_coder.greedy.ncs.NC37;

import java.util.ArrayList;
import java.util.Comparator;

public class NCSolution37 {

    /*
     * 合并区间
     * 
     * 合并区间需要首先对 intervals 中的区间按照左边界排序，按照左边界从小到大的顺序进行排序。在遍历到第 i 个区间时，
     * [left, right]，判断如果第 i + 1 个区间的 l <= 第 i 个区间的 right，那么第 i 个区间和 第 i + 1 个区间的右边界
     * 就可以进行合并，right = max(right, r)，再接着就是判断第 i + 2 个区间的 l <= 更新后的 right，如果是的话，
     * 再进行一次右边界的合并。
     *
     */

    public static class Interval {
        int start;
        int end;
        Interval() { start = 0; end = 0; }
        Interval(int s, int e) { start = s; end = e; }
    }

    public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
        if (intervals == null || intervals.size() == 0){
            return new ArrayList<>();
        }

        Comparator<Interval> comp = new Comparator<Interval>() {
            @Override
            public int compare(Interval o1, Interval o2) {
                if (o1.start != o2.start)
                    return o1.start - o2.start;
                else
                    return o1.end - o2.end;
            }
        };

        intervals.sort(comp);
        ArrayList<Interval> ans = new ArrayList<>();
        int i = 0;

        while (i < intervals.size()){
            int left = intervals.get(i).start;
            int right = intervals.get(i).end;

            while (i < intervals.size() - 1 && intervals.get(i + 1).start <= right){
                right = Math.max(right, intervals.get(i + 1).end);
                i++;
            }

            ans.add(new Interval(left, right));
            i++;
        }

        return ans;
    }
}
